import java.util.ArrayList;
import java.util.Arrays;
import java.util.Hashtable;
import java.util.List;

import org.junit.Test;

public class MyTest {
    public int[][] merge(int[][] intervals) {
        ArrayList<int[]> arrayList=new ArrayList<int[]>();
        Arrays.sort(intervals, (first,second)->(first[0]-second[0]));
        int[] temp=intervals[0];
        for(int i=1;i<intervals.length;i++){
            if(temp[1]<intervals[i][0]){
                arrayList.add(temp);
                temp=intervals[i];
            }else{
                temp[1]=Math.max(temp[1], intervals[i][1]);
            }
        }
        arrayList.add(temp);
        return arrayList.toArray(new int[arrayList.size()][2]);
    }
    
    public List<List<String>> groupAnagrams(String[] strs) {
        Hashtable<String,ArrayList<String>> table=new Hashtable<String,ArrayList<String>>();
        for(String str:strs){
            char[] keyArray=str.toCharArray();
            Arrays.sort(keyArray);
            ArrayList<String> arrayList=table.getOrDefault(new String(keyArray), new ArrayList<String>());
            arrayList.add(str);
            table.put(new String(keyArray), arrayList);
        }
        return new ArrayList<List<String>>(table.values());
    }
    
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int[][] dp=new int[m][n];
        dp[0][0]=grid[0][0];
        for(int i=1;i<n;i++){
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }

    public void sortColors(int[] nums) {
        int redCount=0,whiteCount=0;
        for(int num:nums){
            switch (num) {
                case 0:
                    redCount++;
                    break;
                case 1:
                    whiteCount++;
                    break;
                default:
                    break;
            }
        }
        int i=0;
        while(redCount>0){
            nums[i]=0;
            i++;
            redCount--;
        }
        while(whiteCount>0){
            nums[i]=1;
            i++;
            whiteCount--;
        }
        while(i<nums.length){
            nums[i]=2;
            i++;
        }
    }

    @Test
    public void test(){
        System.out.println(uniquePaths(3, 7));
    }
}
